package problems.daily.y2021m7;

import java.util.HashSet;
import java.util.Set;

/**
 * @author habitplus
 * @since 2021-07-15 15:05
 */
public class T20210715N5 {
    // 567. 字符串的排列
    // 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
    // 换句话说，第一个字符串的排列之一是第二个字符串的 子串 。
    //
    // 提示：
    //      输入的字符串只包含小写字母
    //      两个字符串的长度都在 [1, 10000] 之间
    //
    // 链接：https://leetcode-cn.com/problems/permutation-in-string/
    public boolean checkInclusion(String s1, String s2) {

        int n = s1.length();
        // 建立 s1 的 hash 表
        Set<Character> set = new HashSet<>(n);
        for (char c : s1.toCharArray()) {
            set.add(c);
        }

        char[] chs = s2.toCharArray();
        int j;
        for (int i = 0; i < chs.length; i++) {
            j = i;
            while (j < chs.length && set.contains(chs[j])) {
                j++;
                if (j - i == n) {
                    return true;
                }
            }
        }
        return false;
    }
}
